//dp[i]表示以i位置字符结尾的有效括号的最长长度
//要使有小括号最长，结尾一定是')'
//因此只要考虑结尾字符位')'的情况：
    //如果s[i - 1]为'('，形如.........()，那么dp[i] = dp[i - 2] + 2
    //如果s[i - 1]为')'，形如.........))，
        //如果s[i - 1 - dp[i - 1]]为'('，那么dp[i] = dp[i - 1] + 2
            //如果s[i - 1 - dp[i - 1] - 1]为')'，那么dp[i]还要加上dp[i - 1 - dp[i - 1] - 1 ]
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        int ret = 0;

        if (n >= 2 && s[0] == '(' && s[1] == ')')
        {
            dp[1] = 2;
            ret = 2;
        }
        
        for (int i = 2; i < n; i++)
        {
            if (s[i] == ')')
            {
                if (s[i - 1] == '(')
                    dp[i] = dp[i - 2] + 2;
                else
                    if (i - 1 - dp[i - 1] >= 0 && s[i - 1 - dp[i - 1]] == '(')
                    {
                        dp[i] = dp[i - 1] + 2;
                        if (i - 1 - dp[i - 1] - 1 >= 0)
                            dp[i] += dp[i - 1 - dp[i - 1] - 1 ];
                    }

                ret = max(ret, dp[i]);
            }
        }

        return ret;
    }
};